package com.salim.leetcode.$41;

import lombok.extern.slf4j.Slf4j;

@Slf4j
public class FirstMissingPositive {
    public int firstMissingPositive(int[] nums) {
        for(int i=0;i<nums.length;i++){
            if(nums[i]>nums.length){
                nums[i] = -1;
            }else if(nums[i]<=0){
                continue;
            }else{
                if(nums[i] < nums.length){
                    //交换位置
                    if(nums[i]==nums[nums[i]-1]){
                        if(i == nums[i]-1){
                            continue;
                        }else{
                            nums[i] = -1;
                        }
                    }else{
                        swap(nums,i,nums[i]-1);
                        i--;
                    }
                }
            }
        }
        int sequence = 1;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==sequence){
                sequence++;
            }else if(nums[i]<=0){
                continue;
            }else{
                return sequence;
            }
        }
        return sequence;
    }

    private void swap(int[] nums,int i,int j){
        nums[i] = nums[i]^nums[j];
        nums[j] = nums[j]^nums[i];
        nums[i] = nums[i]^nums[j];
    }

    public static void main(String[] args) {
        FirstMissingPositive f = new FirstMissingPositive();
        log.info("FirstMissingPositive输出结果1：{}", f.firstMissingPositive(new int[]{-1,4,2,1,9,10}));
        log.info("FirstMissingPositive输出结果2：{}", f.firstMissingPositive(new int[]{0,2,2,1,1}));
        log.info("FirstMissingPositive输出结果3：{}", f.firstMissingPositive(new int[]{3,4,-1,1}));
        log.info("FirstMissingPositive输出结果4：{}", f.firstMissingPositive(new int[]{7,8,9,11,12}));
    }
}
